struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr)
    {}
};

class Solution
{
public:
    // 递归实现合并两张有序链表
    ListNode* mergeTwoList(ListNode* l1, ListNode* l2)
    {
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val < l2->val) 
        {
            l1->next = mergeTwoList(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = mergeTwoList(l2->next, l1);
            return l2;
        }
    }
    // 归并排序实现排序链表
    ListNode *sortInList(ListNode *head)
    {
        // 处理边界情况
        if(!head || !head->next) return head;
        // 快慢指针找到链表中间节点
        ListNode *slow, *fast, *prev;
        fast = slow = head;
        while(fast && fast->next)
        {
            prev = slow; // slow的前驱节点
            slow = slow->next;
            fast = fast->next->next;
        }
        // 此时slow位于链表中点，prev作为前驱节点，可以将链表分为两张大小相同的链表
        prev->next = nullptr; 
        // 将两张链表分别排序后，进行合并
        ListNode* l1 = sortInList(head);
        ListNode* l2 = sortInList(slow);
        return mergeTwoList(l1, l2);
    }
};